import java.util.ArrayList;
import java.util.List;

public class PossibleBipartition {

    public static boolean solution(int n,int[][] dislikes){
        boolean[] isVisit=new boolean[n+1];
        boolean[] color=new boolean[n+1];
        List<Integer>[] tempList=new List[n+1];
        for (int i = 1; i <= n; i++) {
            tempList[i]=new ArrayList<>();
        }
        for(int[] d:dislikes){
            tempList[d[0]].add(d[1]);
            tempList[d[1]].add(d[0]);
        }

        for (int i = 1; i <= n; i++) {
            if(!traverse(tempList,i,isVisit,color)){
                return false;
            }
        }

        return true;

    }

    public static boolean traverse(List<Integer>[] graph, int v,boolean[] isvisit,boolean[] color) {
        isvisit[v]=true;
        for(int w:graph[v]){
            if(!isvisit[w]){
                color[w] = !color[v];
                if(!traverse(graph, w,isvisit,color)){
                    return false;
                }
            }else{
                if (color[w] == color[v]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] a= new int[][]{{1,2},{1,3},{2,4}};
        System.out.println(solution(4,a));
    }
}
